<?php
include_once('viper/dao.php');

class viper_server_reindex {
  
public static $n = 100;     // number of users
public static $m = 50;       // number of features 
public static $k = 5;       // # of clusters
public static $iter = 25;   // # of iterations of clustering

public static function reindex(){
$result = viper_server_dbOps::ReadFromUserFeatureScoreDatabase();

$clusters = self::CreateClusters($result);
// var_dump($clusters);

$friends = viper_server_proximityfinder::FindFriends($clusters, $result);
// var_dump($friends);

viper_server_dbOps::WriteToUserQuicklist($friends);
	
}

private static function GetDist($a, $b) {
  $d = 0;
  for ($i = 0; $i < self::$m; $i++) {
    $d = $d + pow(($a['feature'.$i] - $b['feature'.$i]), 2);
  }
  return $d;
}

private static function GetClosestCentroid($point, $centroid) {
  $closest = 0;
  $closest_dist = self::GetDist($point, $centroid[0]);
  for ($j = 1; $j < self::$k; $j++) {
    $cur_dist = self::GetDist($point, $centroid[$j]);
    if ($cur_dist < $closest_dist) {
      $closest = $j;
      $closest_dist = $cur_dist;
    }
  }
  return $closest;
}

private static function AddToCentroid(&$centroid, $cur, $npoints) {
  for ($i = 0; $i < self::$m; $i++) {
    $centroid['feature'.$i] =
        1.0 * ($npoints * $centroid['feature'.$i] + $cur['feature'.$i])
      / ($npoints + 1);
  }
}

private static function RemoveFromCentroid(&$centroid, $cur, $npoints) {
  if ($npoints == 1) {
    return;
 }
  for ($i = 0; $i < self::$m; $i++) {
    $centroid['feature'.$i] = 
        1.0 * ($npoints * $centroid['feature'.$i] - $cur['feature'.$i])
      / ($npoints - 1);
  }
}

private static function RemoveFromArray(&$clusters, $idx) {
  $i = 0;
  for (; $i < count($clusters) && $clusters[$i] != $idx; $i++);
  unset($clusters[$i]);
  $clusters = array_values($clusters);
}

// GoGoGo!
public static function CreateClusters($result) {
  $n = self::$n;
  $m = self::$m;
  $k = self::$k;
  $iter = self::$iter;
  
  // Read from the database
 
  // var_dump($result);

  /*
  // Get the distance array
  $dist = array();
  for ($i = 0; $i < $n; $i++) {
    $ar = array();
    for ($j = 0; $j < $n; $j++) {
      $ar[] = self::GetDist($result[$i], $result[$j]);
    }
    $dist[] = $ar;
  }
  */
  
  // The good stuff: K-Mean Clustering Algorithm
  $clusters_best = array();
  $dist_best = -1;
  for ($iter_count = 0; $iter_count < $iter; $iter_count++) {
    // separate the points into initial clusters
    $numbers = range(0, 99);
    shuffle($numbers);
    
    $clusters = array();
    $centroid = array();
    $incluster = array();
    
    /*
    // Test Code
    for ($i = 0; $i < $k; $i++) {
      $clusters[] = array();
      for ($j = 0; $j < $m; $j++) {
        $centroid[$i]['feature'.$j] = rand(1,10);
      }
    }
    for ($i = 0; $i < $n; $i++) {
      $idx = $i;
      
      // look for the cluster with the closest centroid
      $closest = 0; //self::GetClosestCentroid($result[$idx], $centroid);
      
      // add the point to the cluster, and update the centroid
      $clusters[$closest][] = $idx;
      $incluster[$idx] = $closest;
    }*/
   
    
    for ($i = 0; $i < $k; $i++) {
      $idx = $numbers[$i];
      $clusters[$i] = array();
      $clusters[$i][] = $idx;
      for ($j = 0; $j < $m; $j++) {
        $centroids[$i]['feature'.$j] =
            1.0*$result[$clusters[$i][0]]['feature'.$j];
      }
      $incluster[$idx] = $i;
    }
    
    // put the rest of the points into the closest cluster
    for ($i = $k; $i < $n; $i++) {
      $idx = $numbers[$i];
      
      // look for the cluster with the closest centroid
      $closest = self::GetClosestCentroid($idx, $result, $centroid);
      
      // add the point to the cluster, and update the centroid
      self::AddToCentroid($centroids[$closest],
                          $result[$idx],
                          count($clusters[$closest]));
      $clusters[$closest][] = $idx;
      $incluster[$idx] = $closest;
    }
    /*
    for ($j = 0; $j < $k; $j++) {
      echo '<br />Calculated centroid: ';
      for ($i = 0; $i < $m; $i++)
        echo '  '.$centroids[$j]['feature'.$i];
      echo '<br />Actual centroid: ';
      for ($i = 0; $i < $m; $i++) {
        $sum = 0;
        for ($blah = 0; $blah < count($clusters[$j]); $blah++) {
          $sum = $sum + $result[$clusters[$j][$blah]]['feature'.$i];
        }
        echo '  '.$sum / count($clusters[$j]);
      }
        
    }
    */
    
    // var_dump($clusters);
    $nsteps = 0;
    $converge = false;
    while (!$converge) {
      // echo 'New iteration <br />';
      $nsteps++;
      $converge = true;
      // For each sample, reassign it to the cluster with the closest centroid
      for ($i = 0; $i < $n; $i++) {
        $cur = $incluster[$i]; // echo $cur; 
        $closest = self::GetClosestCentroid($result[$i], $centroids);
        // var_dump($result[$idx]);
        // var_dump($centroid);
  
        // echo '    and the closest is   '; echo $closest; echo '<br />';
        if ($closest != $cur) {
          // echo 'Fuck point '.$i.'<br />';
          $converge = false;
          
          // update centroids
          self::AddToCentroid($centroids[$closest],
                               $result[$i],
                               count($clusters[$closest]));
          self::RemoveFromCentroid($centroids[$cur],
                                   $result[$i],
                                   count($clusters[$cur]));
          
          // remove the sample from the old cluster
          self::RemoveFromArray($clusters[$cur], $i);
          // add the sample to the new cluster
          $clusters[$closest][] = $i;
          
          // Update the cluster lookup
          $incluster[$i] = $closest;
        }
      }
    }
    
    // Calculate the sum of the distances from each point to
    // centroid of its cluster
    $dist_cur = 0;
    for ($idx = 0; $idx < $k; $idx++) {
      // Find the size of the cluster
      $csize = count($clusters[$idx]);
    
      for ($i = 0; $i < $csize; $i++) {
        $cur = $clusters[$idx][$i];
        $dist_cur = $dist_cur +
                    sqrt(self::GetDist($result[$cur], $centroids[$idx]));
      }
    }
    
    // Update the optimal cluster
    if ($dist_best == -1 || $dist_best > $dist_cur) {
      $clusters_best = $clusters;
      $dist_best = $dist_cur;
    }
    // echo $nsteps;
    /*
    for ($j = 0; $j < $k; $j++) {
      echo '<br />Calculated centroid: ';
      for ($i = 0; $i < $m; $i++)
        echo '  '.$centroids[$j]['feature'.$i];
      echo '<br />Actual centroid: ';
      for ($i = 0; $i < $m; $i++) {
        $sum = 0;
        for ($blah = 0; $blah < count($clusters[$j]); $blah++) {
          $sum = $sum + $result[$clusters[$j][$blah]]['feature'.$i];
        }
        echo '  '.$sum / count($clusters[$j]);
      }
        
    }
    
   
    // var_dump($clusters);
    var_dump($centroids);
    for ($i = 0; $i < $n; $i++) {
      echo 'Point '.$i; echo 'in cluster '.$incluster[$i];
      echo '<br />';
      for ($j = 0; $j < $k; $j++) {
        echo '   '.self::GetDist($result[$i], $centroids[$j]);
        echo '<br />';
      }
    }
    echo '<br /><br />This is the entire table<br /><br />';
    var_dump($result);
    */
  }  // End of loop for each iteration of algorithm
  return $clusters_best;
}

}  // Class viper_server_clusters

?>
  